package leetCode;

/**
 * 76. 最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring/description/
 */
class Solution {
    //老师的版本
    public String minWindow2(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        //hash1存放t数组字符的频次
        int[] hash1 = new int[128];
        int kinds = 0;//种类
        for(char ch : t) {
            if(hash1[ch] == 0) kinds++;
            hash1[ch]++;
        }
        int[] hash2 = new int[128];
        int minLen = Integer.MAX_VALUE, begin = -1;
        for(int left = 0, right = 0, count = 0; right < ss.length(); right++) {
            //进窗口
            char in = s[right];
            hash2[in]++;
            if(hash2[in] == hash1[in]) count++;
            //判断
            while(count == kinds) {
                //更新值
                if(right - left + 1 < minLen) {
                    begin = left;
                    minLen = right - left + 1;
                }
                char out = s[left];
                if(hash2[out] == hash1[out]) count--;
                //出窗口
                hash2[out]--;
                left++;
            }
        }
        if(begin == -1) return new String();
        else return ss.substring(begin, begin + minLen);
    }

    //自己的版本
    public static String minWindow1(String ss, String tt) {
        String ret = "";
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int lenT = t.length;
        int[] hash1 = new int[58];
        //把tt字符都存进容器里
        for(char ch : t) hash1[ch - 'A']++;
        //滑动窗口中的存放的字符
        int[] hash2 = new int[58];
        for(int left = 0, right = 0, count = 0, len = Integer.MAX_VALUE; right < ss.length(); right++) {
            //入窗口
            hash2[s[right] - 'A']++;
            if(hash2[s[right] - 'A'] <= hash1[s[right] - 'A']) count++;//维护count
            while(count >= lenT) {
                //更新值
                if(len > right - left + 1) {
                    ret = ss.substring(left, right + 1);
                    len = right - left + 1;
                }
                if(hash2[s[left] - 'A'] <= hash1[s[left] - 'A']) count--;//维护count
                //出窗口
                hash2[s[left] - 'A']--;
                left++;
            }
        }
        return ret;
    }
}